package easy;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class q160 {

    public static void main(String[] args) {

    }

    /**
     * 双指针
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getBestIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        Map<ListNode, Integer> map = new HashMap<>();

        if (headA == null || headB == null) {
            return null;
        }

        while (headA != null) {
            map.put(headA, 1);
            headA = headA.next;
        }

        while (headB != null) {
            if (map.containsKey(headB)) {
                return headB;
            }
            headB = headB.next;
        }

       return null;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();

        if (headA == null || headB == null) {
            return null;
        }

        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }

        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }

        ListNode a = stackA.peek();
        ListNode b = stackB.peek();

        if (!a.equals(b)) {
            return null;
        }

        ListNode result = null;
        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            a = stackA.pop();
            b = stackB.pop();
            if (!a.equals(b)) {
                break;
            }
            result = a;
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            this.val = x;
            this.next = null;
        }
    }

}
